// Copyright 2011 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package main

import (
	"exp/ebnf"
	"fmt"
	"github.com/cznic/strutil"
	"sort"
	"strconv"
	"text/scanner"
	"unicode"
)

type options struct {
	Tokens map[string]string
}

type task struct {
	errf  func(scanner.Position, string)
	f     strutil.Formatter
	grm   ebnf.Grammar
	names map[string]bool // false: nonterminal, true: terminal
	opts  *options
	start string
}

func (t *task) safeinsert(name string, terminal bool) (existed bool) {
	if _, existed := t.names[name]; !existed {
		t.names[name] = terminal
	}
	return
}

var nopos = scanner.Position{}

func (t *task) insert(name string, terminal bool) {
	if t.safeinsert(name, terminal) {
		t.errf(nopos, fmt.Sprintf("%q redeclared", name))
	}
}

func isNonTerminal(name string) bool {
	return unicode.IsUpper(rune(name[0]))
}

func (t *task) inventName(name string) (n string) {
	if len(t.names) == 0 { // bootstrap
		for x := range t.grm {
			if isNonTerminal(x) {
				t.insert(x, false)
			}
		}
		for _, x := range t.opts.Tokens {
			t.insert(x, true)
		}
	}
	for i := 1; ; i++ {
		n = name + "_" + strconv.Itoa(i)
		if _, ok := t.names[n]; !ok {
			t.names[n] = false
			return
		}
	}
	panic("unreachable")
}

func (t *task) expr(in *ebnf.Expression) (out ebnf.Expression) {
	out = *in
	switch out.(type) {
	default:
		t.errf(out.Pos(), fmt.Sprintf("%s internal error %T %#v", me(), out, out))
	case nil:
		// nop
	case *ebnf.Name:
		out = ebnf.Alternative{out}
		*in = out
	case ebnf.Alternative:
		// nop
	case ebnf.Sequence:
		out = ebnf.Alternative{out}
		*in = out
	case *ebnf.Token:
		out = ebnf.Alternative{out}
		*in = out
	case *ebnf.Option:
		out = ebnf.Alternative{out}
		*in = out
	}
	return
}

func (t *task) rewriteRepetitions() {
	var walk func(string, ebnf.Expression) ebnf.Expression

	walk = func(name string, expr ebnf.Expression) ebnf.Expression {
		switch x := expr.(type) {
		default:
			t.errf(expr.Pos(), fmt.Sprintf("%s internal error %T %#v", me(), expr, expr))
			return nil
		case nil:
			return nil
		case *ebnf.Name:
			s := x.String
			if !isNonTerminal(s) {
				t.safeinsert(s, true)
			}
			return x
		case ebnf.Sequence:
			for i, item := range x {
				x[i] = walk(name, item)
			}
			return x
		case *ebnf.Option:
			return &ebnf.Option{x.Lbrack, walk(name, t.expr(&x.Body))}
		case ebnf.Alternative:
			for i, item := range x {
				x[i] = walk(name, item)
			}
			return x
		case *ebnf.Token:
			s := x.String
			switch s[0] {
			case '\'', '"':
				return x
			}
			render, ok := t.opts.Tokens[s]
			if !ok {
				render = fmt.Sprintf("'%s'", s)
				switch len(s) == 1 && s[0] < 127 && unicode.IsPrint(rune(s[0])) {
				case true:
					t.safeinsert(fmt.Sprintf("\\x%2x", s[0]), true)
				case false:
					render = fmt.Sprintf("%q", s)
					t.errf(x.Pos(), "missing rendering for token "+render)
				}
			} else {
				t.safeinsert(render, true)
			}
			return &ebnf.Token{x.Pos(), render}
		case *ebnf.Group:
			return &ebnf.Group{x.Lparen, walk(name, t.expr(&x.Body))}
		case *ebnf.Repetition:
			newname := t.inventName(name)
			repname := &ebnf.Name{x.Lbrace, newname}
			rep := walk(newname, t.expr(&x.Body)).(ebnf.Alternative)
			switch y := rep[0].(type) {
			default:
				t.errf(expr.Pos(), fmt.Sprintf("%s internal error %T %#v", me(), y, y))
			case ebnf.Sequence:
				rep[0] = append(ebnf.Sequence{&ebnf.Name{x.Lbrace, newname}}, y...)
			case *ebnf.Token:
				rep[0] = append(ebnf.Sequence{&ebnf.Name{x.Lbrace, newname}}, y)
			case *ebnf.Name:
				rep[0] = append(ebnf.Sequence{&ebnf.Name{x.Lbrace, newname}}, y)
			}
			t.grm[newname] = &ebnf.Production{repname, append(ebnf.Alternative{nil}, rep...)}
			return &ebnf.Name{x.Lbrace, newname}
		}
		panic("unreachable")
	}

	for name, prod := range t.grm {
		if isNonTerminal(name) {
			prod.Expr = walk(name, t.expr(&prod.Expr))
		}
	}
}

func (t *task) prolog() {
	var names []string
	for name := range t.names {
		if name[0] != '\\' && !isNonTerminal(name) {
			names = append(names, name)
		}
	}
	sort.Strings(names)
	for _, name := range names {
		t.f.Format("\n%%token %s", name)
	}
	t.f.Format("\n\n%%start %s\n\n%%%%", t.start)
}

func (t *task) emit() {
	var walk func(string, ebnf.Expression)

	rule := 0
	walk = func(name string, expr ebnf.Expression) {
		switch x := expr.(type) {
		default:
			t.errf(expr.Pos(), fmt.Sprintf("%s internal error %T %#v", me(), expr, expr))
		case nil:
			rule++
			t.f.Format("\n\t  /* empty */ // (%d)", rule)
		case *ebnf.Name:
			t.f.Format("%s", x.String)
		case ebnf.Sequence:
			if len(x) == 0 {
				rule++
				t.f.Format("/* empty */\t// (%d)", rule)
				return
			}

			for i, item := range x {
				if i != 0 {
					t.f.Format(" ")
				}
				walk(name, item)
			}
		case ebnf.Alternative:
			empty := false
			for _, item := range x {
				if empty = item == nil; empty {
					rule++
					t.f.Format("\n\t  /* empty */\t// (%d)", rule)
					break
				}
			}
			for i, item := range x {
				if item == nil {
					continue
				}

				t.f.Format("\n\t")
				if empty || i != 0 {
					t.f.Format("| ")
				} else {
					t.f.Format("  ")
				}
				walk(name, item)
				rule++
				t.f.Format("\t// (%d)", rule)
			}
		case *ebnf.Token:
			t.f.Format("%s", x.String)
		}
	}

	names := []string{}
	for name := range t.grm {
		if isNonTerminal(name) {
			names = append(names, name)
		}
	}
	sort.Strings(names)
	for _, name := range names {
		expr := t.grm[name].Expr
		n := 0
		if a, ok := expr.(ebnf.Alternative); ok {
			n = len(a)
		}
		t.f.Format("\n\n")
		_ = n
		//t.f.Format("// %d\n", n)
		t.f.Format("%s:", name)
		walk(name, expr)
		t.f.Format("\n;")
	}
	t.f.Format("\n")
}

func (t *task) flatten() {
	var in, out []ebnf.Expression
	var expand func(string, ebnf.Expression)

	expand = func(name string, expr ebnf.Expression) {
		switch x := expr.(type) {
		case nil:
			out = append(out, expr)
		default:
			t.errf(expr.Pos(), fmt.Sprintf("%s %q internal error %T %#v", me(), name, expr, expr))
		case ebnf.Sequence:
			for i, item := range x {
				switch y := item.(type) {
				case nil:
					// nop
				default:
					var p scanner.Position
					if y != nil {
						p = y.Pos()
					}
					t.errf(p, fmt.Sprintf("%s %q internal error %T %#v", me(), name, y, y))
					return
				case *ebnf.Token:
					// nop
				case *ebnf.Name:
					// nop
				case *ebnf.Option:
					n := len(x)
					with := make(ebnf.Sequence, n)
					copy(with, x)
					with[i] = y.Body
					without := make(ebnf.Sequence, n-1)
					copy(without, x[:i])
					if i < n-1 {
						copy(without[i:], x[i+1:])
					}
					in = append(in, with)
					in = append(in, without)
					return
				case ebnf.Alternative:
					n := len(x)
					for _, item := range y {
						with := make(ebnf.Sequence, n)
						copy(with, x)
						with[i] = item
						in = append(in, with)
					}
					return
				case *ebnf.Group:
					n := len(x)
					with := make(ebnf.Sequence, n)
					copy(with, x)
					with[i] = y.Body
					in = append(in, with)
					return
				case ebnf.Sequence:
					with := ebnf.Sequence{}
					if i != 0 {
						with = append(with, x[:i]...)
					}
					if len(y) != 0 {
						with = append(with, y...)
					}
					if i+1 < len(x) {
						with = append(with, x[i+1:]...)
					}
					if len(with) != 0 {
						in = append(in, with)
						return
					}
				}
			}
			out = append(out, x)
		case *ebnf.Name:
			out = append(out, x)
		case *ebnf.Token:
			out = append(out, x)
		case *ebnf.Option:
			in = append(out, x.Body)
		case ebnf.Alternative:
			if len(x) != 1 {
				t.errf(x.Pos(), fmt.Sprintf("%s %q internal error %T %#v", me(), name, x, x))
			}
			in = append(out, x[0])
		}
	}

	for name, prod := range t.grm {
		if isNonTerminal(name) {
			expr := prod.Expr
			if expr == nil {
				continue
			}

			if _, ok := expr.(ebnf.Alternative); !ok {
				t.errf(expr.Pos(), fmt.Sprintf("%s %q internal error %T %#v", me(), name, expr, expr))
				continue
			}

			in, out = expr.(ebnf.Alternative), []ebnf.Expression{}
			for {
				n := len(in)
				if n == 0 {
					break
				}

				alt := in[n-1]
				in = in[:n-1]
				expand(name, alt)
			}
			t.grm[name] = &ebnf.Production{prod.Name, ebnf.Alternative(out)}
		}
	}
}
